﻿/******************************************************************************
	Cobalt - utility libraries for building XNA games
	Copyright (C) 2008 Philip Djonov

	This program is free software; you can redistribute it and/or modify it
	under the terms of the GNU General Public License as published by the Free
	Software Foundation; either version 2 of the License, or (at your option)
	any later version.

	This program is distributed in the hope that it will be useful, but
	WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
	or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
	for more details.

	You should have received a copy of the GNU General Public License along
	with this program; if not, write to the
	
		Free Software Foundation, Inc.
		51 Franklin Street, Fifth Floor
		Boston, MA  02110-1301, USA.
******************************************************************************/

using System;
using System.Collections.Generic;

using Microsoft.Xna.Framework;
using Microsoft.Xna.Framework.Content.Pipeline;
using Microsoft.Xna.Framework.Content.Pipeline.Graphics;
using Microsoft.Xna.Framework.Graphics;

namespace Cobalt.Content.Pipeline.Graphics.Imaging
{

	public static class ImagePacker
	{
		private const int Padding = 1;

		public static PackedSheet Pack( IEnumerable<BitmapContent> images )
		{
			var sourceImages = new List<BitmapContent>( images );

			if( sourceImages.Count == 0 )
				return new PackedSheet( 0, 0 );

			sourceImages.Sort( ( a, b ) =>
				(b.Height * 1024 + b.Width) -
				(a.Height * 1024 + a.Width) );

			int width = GuessWidth( sourceImages );
			int height = 0;

			var placements = new Dictionary<BitmapContent, Rectangle>();
			sourceImages.ForEach( a => PlaceImage( a, placements, width, ref height ) );

			height = Helpers.RoundUpToPowerOf2( height );

			var ret = new PackedSheet( width, height );

			foreach( var p in placements )
			{
				BitmapContent.Copy( p.Key, new Rectangle( 0, 0, p.Key.Width, p.Key.Height ),
					ret.SheetImage, p.Value );
				ret.ImagePositions.Add( p.Key, p.Value );
			}

			return ret;
		}

		private static void PlaceImage( BitmapContent image, Dictionary<BitmapContent, Rectangle> placements,
			int width, ref int height )
		{
			for( int x = 0, y = 0; ; )
			{
				Rectangle? overlap = CheckForIntersection(
					placements.Values, image, x, y );

				if( overlap == null )
				{
					placements.Add( image,
						new Rectangle( x, y, image.Width, image.Height ) );
					break;
				}

				//skip across
				x += overlap.Value.Width;

				if( x + image.Width > width )
				{
					x = 0;
					y++;
				}
			}

			Rectangle rc = placements[image];

			if( rc.Bottom > height )
				height = rc.Bottom;
		}

		static private Rectangle? CheckForIntersection( IEnumerable<Rectangle> usedRectangles, BitmapContent image, int x, int y )
		{
			Rectangle rcTest = new Rectangle( x, y, image.Width, image.Height );
			rcTest.Inflate( Padding, Padding );

			foreach( var rc in usedRectangles )
			{
				rc.Inflate( Padding, Padding );

				if( rcTest.IntersectsWith( rc ) )
					return rc;
			}

			return null;
		}

		private static int GuessWidth( List<BitmapContent> sourceImages )
		{
			int maxWidth = 0;
			long totalWidth = 0;

			sourceImages.ForEach( i =>
			{
				int w = i.Width + Padding * 2;

				totalWidth += w;
				if( maxWidth < w ) maxWidth = w;
			} );

			int averageWidth = (int)(totalWidth + sourceImages.Count) /
				sourceImages.Count;
			maxWidth = Helpers.RoundUpToPowerOf2( maxWidth );

			//assume a square grid of average-width images
			int guess = averageWidth * (int)Math.Ceiling(
				Math.Sqrt( sourceImages.Count ) );

			if( Helpers.IsPowerOf2( guess ) )
				//make sure we don't return something too small for the biggest image
				return Math.Max( guess, maxWidth );

			//find the powers of two that bound our guess
			int lowGuess = Helpers.RoundUpToPowerOf2( guess / 2 );
			int highGuess = Helpers.RoundUpToPowerOf2( guess );

			//snap it to the nearest of the values
			//(so as to avoid cases where we waste a bunch rounding up)
			if( highGuess > 1024 )
				guess = guess - lowGuess < highGuess - guess ? lowGuess : highGuess;
			else
				guess = highGuess;

			//again, make sure we don't return something too small for the biggest image
			return Math.Max( guess, maxWidth );
		}
	}

	public class PackedSheet
	{
		public PixelBitmapContent<Color> SheetImage { get; private set; }
		public Dictionary<BitmapContent, Rectangle> ImagePositions { get; private set; }

		public PackedSheet( int width, int height )
		{
			SheetImage = new PixelBitmapContent<Color>( width, height );
			ImagePositions = new Dictionary<BitmapContent, Rectangle>();
		}
	}

}